package com.ljx.List;

import com.ljx.Dynamic.ListNode;

/**
 * @author 李加喜
 * @Package com.ljx.List
 * @date 2021-11-18 10:44
 */
// 判断一个链表是否是回文链表
public class HuiWenList {
    public static void main(String[] args) {

    }
    /**
     * 方法一 讲链表进行反转 定义两个指针分别指向这两个节点  判断链表的节点是否是相等  就可以判断是否是会问链表
     *
     * 方法二 使用递归
     *
     * 方法三 使用快买指针+反转链表操作
     */
    // 递归方式处理反转
    ListNode left;
    public boolean isPalindrome(ListNode head) {
        left=head;
        return traverse(head);
    }

    /**
     * 判断
     * @param right
     * @return
     */
    private boolean traverse(ListNode right) {
        if(right==null){
            return true;
        }
        // 一直走到最后面的节点
        boolean res=traverse(right.next);
        res=res && (right.val==left.val);
        left=left.next;
        return res;
    }
    boolean isPalindrome1(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null){
            slow = slow.next;
        }
        ListNode left = head;
        ListNode right = reverse(slow);
        while (right != null) {
            if (left.val != right.val){
                return false;
            }
            left = left.next;
            right = right.next;
        }

        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            // 下面这两行进行了反转
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
